Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Solution:

  1. public class Solution {
  2.   public int majorityElement(int[] nums) {
  3.     Integer m = null;
  4.     int c = 0;
  6.     for (int i = 0; i < nums.length; i++) {
  7.       if (m != null && m == nums[i]) {
  8.         c++;
  9.       } else if (c == 0) {
  10.         m = nums[i];
  11.         c = 1;
  12.       } else {
  13.         c--;
  14.       }
  15.     }
  17.     c = 0;
  18.     for (int i = 0; i < nums.length; i++) {
  19.       if (m != null && m == nums[i]) {
  20.         c++;
  21.       }
  22.     }
  24.     if (c > nums.length / 2) {
  25.       return m;
  26.     } else {
  27.       return -1;
  28.     }
  29.   }
  30. }